class KnightTour:
    def __init__(self, n):
        self.n = n
        self.board = [[-1 for _ in range(n)] for _ in range(n)]
        self.moves = [(-2, -1), (-1, -2), (1, -2), (2, -1),
                      (2, 1), (1, 2), (-1, 2), (-2, 1)]

    def is_valid(self, x, y):
        return 0 <= x < self.n and 0 <= y < self.n and self.board[x][y] == -1

    def get_next_moves(self, x, y):
        # Warnsdorff’s heuristic: prioritize cells with least onward moves
        next_moves = []
        for dx, dy in self.moves:
            nx, ny = x + dx, y + dy
            if self.is_valid(nx, ny):
                count = sum(1 for ddx, ddy in self.moves
                            if self.is_valid(nx + ddx, ny + ddy))
                next_moves.append((count, nx, ny))
        next_moves.sort()
        return [(nx, ny) for _, nx, ny in next_moves]

    def solve(self, x, y, step=0):
        self.board[x][y] = step
        if step == self.n * self.n - 1:
            return True

        for nx, ny in self.get_next_moves(x, y):
            if self.solve(nx, ny, step + 1):
                return True

        self.board[x][y] = -1  # 回溯
        return False

    def get_board(self):
        return self.board
